package Sort;

import java.util.Arrays;
import java.util.Stack;

public class Sort {
    public static void insertSort(int[] array){
        for (int i = 1; i < array.length; i++) {
            int temp = array[i];
            int j = i-1;
            for (; j >= 0; j--) {
                if(array[j]>temp){
                    array[j+1] =array[j];
                }else{
                    break;
                }
            }
            array[j+1]=temp;
        }
    }

    public static void shellSort(int[] array){
        int gap = array.length;
        while(gap>1){
            gap/=2;
            Shell(array,gap);
        }
    }

    private static void Shell(int[] array,int gap){
        for (int i = gap; i < array.length; i++) {
            int temp = array[i];
            int j = i-gap;
            for (; j >= 0; j-=gap) {
                if(array[j]>temp){
                    array[j+gap] =array[j];
                }else{
                    break;
                }
            }
            array[j+gap]=temp;
        }
    }

    public static void selectSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i+1; j < array.length; j++) {
                if(array[j]<array[minIndex]){
                    minIndex = j;
                }
            }
            swap(array,i,minIndex);
        }
    }

    public static void selectSort2(int[] array){
        int left = 0 ;
        int right = array.length-1;
        while(left<right){
            int minIndex = left;
            int maxIndex = left;
            for (int i = left+1; i <=right; i++) {
                if(array[i]<array[minIndex]){
                    minIndex = i;
                }
                if(array[i]>array[maxIndex]){
                    maxIndex = i;
                }
            }
            swap(array,left,minIndex);
            if(maxIndex==left){
                maxIndex = minIndex;
            }
            swap(array,right,maxIndex);
            left++;
            right--;
        }
    }

    private static void swap(int[] array,int a,int b){
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

    public static void heapSort(int[] array){
        createBigHeap(array);
        int end = array.length-1;
        while(end>0){
            swap(array,0,end);
            siftDown(array,0,end);
            end--;
        }
    }

    private static void createBigHeap(int[] array){
        for(int parent = (array.length-1-1)/2;parent>=0;parent--){
            siftDown(array,parent,array.length);
        }
    }

    private static void siftDown(int[] array,int parent,int end){
        int child=parent*2+1;
        while(child<end){
            if(child+1<end&&array[child+1]>array[child]){
                child++;
            }
            if(array[child]>array[parent]){
                swap(array,child,parent);
                parent = child;
                child= parent*2 +1;
            }else{
                break;
            }
        }
    }

    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            boolean flag = false;//标记
            for (int j = 0; j < array.length-i-1; j++) {
                if(array[j]>array[j+1]){
                    swap(array,j+1,j);
                    flag=true;//如果走不到这一步
                }
            }
            if(flag==false){//说明已经有序，则从这里退出方法
                return ;
            }
        }
    }

    public static void quickSort(int[] array) {//为了保证接口的统一性，这里只传一个参数
        quick(array,0,array.length-1);
    }

    private static void quick(int[] array,int start,int end ){
        if(start>=end){
            return ;
        }
        int index = midOfThree(array,start,end);
        swap(array,index,start);
        int pivot = partition(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }

    private static int midOfThree(int[] array, int left , int right){//三数取中，优化基准的位置
        int mid = (left+right)/2;
        if (array[left] < array[right]) {
            if(array[mid]<array[left]){
                return left;
            }else if(array[mid]>array[right]){
                return right;
            }else{
                return mid;
            }
        }else{
            if(array[mid]>array[left]){
                return left;
            }else if(array[mid]<array[right]){
                return right;
            }else{
                return mid;
            }
        }
    }

    private static int partition2(int[] array,int left ,int right) {//Hoare交换法求基准
        int key = array[left];//选left下标的数作为基准
        int i = left;//记录下左边下标
        while(left<right){
            while(left<right && array[right]>=key){//多加个判断防止越界
                right--;//没遇到比key小的就往前走
            }
            while(left<right && array[left]<=key){
                left++;//没遇到比key大的就往后走
            }
            swap(array,left,right);//遇到大的在前，小的再后，此时就可以交换两个下标的值
        }
        swap(array,i,right);//相遇之后交换基准和相遇的地方
        return left;//返回基准，这样就可以做到，调整顺序，和找基准
    }

    private static int partition(int[] array,int left ,int right) {//挖坑法
        int key = array[left];//选left下标的数作为基准
        while(left<right){
            while(left<right&&array[right]>key){
                right--;
            }
            array[left] = array[right];
            while(left<right&&array[left]<key){
                left++;
            }
            array[right] = array[left];
        }
        array[left]=key;
        return left;//挖坑法的优先度更高，因为会省去交换的操作，从而达到减小复杂度的效果
    }

    private static int partition3(int[] array,int left,int right){//前后指针法
        int front = left;
        int rear = left +1;
        while(rear<=right){
            if(array[rear]<array[left]&&array[++front]!=array[rear]){
                swap(array,rear,front);
            }
            rear++;
        }
        swap(array,front,left) ;
        return front;
    }

    public static void quickSortNor(int[] array) {
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length-1;
        int pivot = partition(array,left,right);
        if(pivot-1>left){
            stack.push(left);
            stack.push(pivot-1);
        }
        if(pivot+1<right){
            stack.push(pivot+1);
            stack.push(right);
        }
        while(!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
            pivot = partition(array,left,right);
            if(pivot-1>left){
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot+1<right){
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }

    public static void mergeSort(int[] array) {
        mergeSortFunction(array,0,array.length-1);
    }

    private static void mergeSortFunction(int[] array , int left ,int right) {
        if(left >=right){
            return ;
        }
        int mid = (left + right )/2;
        mergeSortFunction(array,left,mid);
        mergeSortFunction(array,mid+1,right);
        merge(array,left,right,mid);
    }

    private static void merge(int[] array,int left , int right , int mid) {
        int[] tempArray = new int[right-left+1];
        int s1 = left;
        int s2 = mid +1 ;
        int i = 0 ;
        while(s1<=mid&&s2<=right){
            if(array[s1]>=array[s2]){
                tempArray[i] = array[s2];
                i++;
                s2++;
            }else{
                tempArray[i] = array[s1];
                i++;
                s1++;
            }
        }
        while (s1<=mid){
            tempArray[i]=array[s1];
            i++;
            s1++;
        }
        while (s2<=right){
            tempArray[i]=array[s2];
            i++;
            s2++;
        }
        for (int j = 0; j < tempArray.length; j++) {
            array[j+left] = tempArray[j];
        }
    }

    public static void mergeSortNor(int[] array) {
        int gap = 1 ;
        while (gap<array.length){
            for (int i = 0; i < array.length; i+=2*gap) {
                int left = i ;
                int mid = left + gap -1;
                int right = mid + gap;
                if(mid>=array.length){
                    mid = array.length-1;
                }
                if(right>=array.length) {
                    right = array.length-1;
                }
                merge(array,left,right,mid);
            }
            gap=gap*2;
        }
    }

}
